This invention relates to electronic circuits which process arrays of data.
By an array of data is herein meant data which is arranged in multiple rows and multiple columns. Such an array of data occurs in disk systems where the respective columns of the array are written in parallel onto separate disks; and thereafter, the respective columns of the array are read back in parallel from the separate disks.
Examples of the above array processing disk systems are found in the following patents and technical papers: 1) U.S. Pat. No. 4,722,085 by Flora et al entitled "High Capacity Disk Storage System Having Unusually High Fault Tolerance Level and Bandpass"; 2) U.S. Pat. No. 4,775,978 by Hartness entitled "Data Error Correction System"; 3) "RAID Architecture Provides Increased Throughput and Capacity" by Ernest Ohrenstein, Computer Technology Review, Spring 1989, pages 37-41; 4) "A Case For Redundant Arrays of Inexpensive Disks (RAID)", by Patterson, Gibson, and Katz, Report No. VCB/CSD 87/39/ from the Computer Science Division of the University of California at Berkeley, December 1987, pages 1-24; and, 5) "RAID 5 Architecture Provides Economical Failsafe Disc Storage" by M. Anderson, EDN, June 1991, pages 141-143.
However, in all the above cited references, the array processing circuits which are disclosed have various drawbacks and limitations. For example, in Flora, each row in the array is required to have an error code which both detects when an error occurs in the row and corrects that error. Using the Flora system, both the error checking and correcting is done one row at a time. But, that is a relatively slow process in comparison to present invention wherein only one error check is performed on each column; and, only error correcting is performed row-by-row. Further, to be able to check for errors on each column and only correct errors row-by-row requires an entirely different array processing circuit than that which is disclosed by Flora.
In Hartness, the errors are detected on each column and corrected row-by-row. However, to achieve the above result, Hartness requires every column of the array, including the parity column, to have an error check code (ECC) as the last entry in the column. Consequently, the parity column in the array cannot be the same length as the other columns; the parity column requires one entry for each row in the other columns plus it requires an extra entry for the ECC character. Having an unequal number of entries in every column is highly undesirable because it forces the disks on which the columns are stored to have different formats and thus be non-interchangeable.
Also in Hartness, when a column of data has an error, every column including the erroneous column is processed in order to correct the error. By comparison, the present invention corrects errors with a completely different method and circuit in which the erroneous column is ignored and excluded from processing.
Further, in order for the Hartness circuitry to even operate, all of the disks on which an array of data is stored must rotate in synchronization such that each disk reads and/or writes a respective word of the same row at the same time instant. This constraint makes the Hartness circuits very impractical since commercially available disks rotate independently with respect to each other.
Ohrenstein discloses a disk array system called RAID (Redundant Array of Inexpensive Disks). However, Ohrenstein merely discusses various system level functional aspects of the RAID system--such as its fault tolerance and high throughput; Ohrenstein does not teach or describe any circuits which are needed to actually build a RAID system. In Ohrenstein, the only diagram of the RAID system is disclosed in FIG. 1; and there, the entire control circuitry for processing the array of data to/from the disks is shown as one black box.
Likewise, in the UC Berkeley reference, additional RAID systems are disclosed and classified as RAID level one thru RAID level five. But here again, the description and classification is from a functional viewpoint at a system level; and, no circuitry for building a system is shown. See, in particular, the system diagrams of FIGS. 1 and 2, and the RAID data distribution diagrams of FIGS. 3 and 4.
Anderson, in his above cited article, merely evaluates the RAID-5 system and concludes that it creates the smallest bottleneck when errors are corrected because the parity column is distributed over several disks instead of one. But again in this evaluation, no diagrams of any RAID circuitry is provided.
Accordingly, a primary object of the present invention is to provide an actual electronic circuit with all of the intricate details that are needed to process arrays of data to/from an array of disks, and which has none of the above identified drawbacks.